;(function () {
  function descriptor(object) {
    var desc = {},
      p
    for (p in object) {
      desc[p] = {
        value: object[p],
        writable: true,
        enumerable: true,
        configurable: true,
      }
    }
    return desc
  }

  function merge(proto, object) {
    return Object.create(proto, descriptor(object))
  }

  function extend(proto, object) {
    var p
    for (p in object) {
      proto[p] = object[p]
    }
  }
  /*
   * File: Graph.js
   *
   */

  /*
 Class: Graph

 A Graph Class that provides useful manipulation functions. You can find more manipulation methods in the <Graph.Util> object.

 An instance of this class can be accessed by using the *graph* parameter of any tree or graph visualization.

 Example:

 (start code js)
   //create new visualization
   var viz = new $jit.Viz(options);
   //load JSON data
   viz.loadJSON(json);
   //access model
   viz.graph; //<Graph> instance
 (end code)

 Implements:

 The following <Graph.Util> methods are implemented in <Graph>

  - <Graph.Util.getNode>
  - <Graph.Util.eachNode>
  - <Graph.Util.computeLevels>
  - <Graph.Util.eachBFS>
  - <Graph.Util.clean>
  - <Graph.Util.getClosestNodeToPos>
  - <Graph.Util.getClosestNodeToOrigin>

*/

  var Graph = function (opt) {
    this.opt = merge(
      {
        node: {},
      },
      opt || {}
    )
    this.nodes = {}
    this.edges = {}
  }

  Graph.fromJSON = function (json) {
    var nodes = json.nodes,
      edges = json.edges,
      Node = Graph.Node,
      Edge = Graph.Edge,
      graph = new Graph(),
      k

    for (k in nodes) {
      nodes[k] = Node.fromJSON(nodes[k])
    }

    graph.nodes = nodes

    for (k in edges) {
      edges[k] = Edge.fromJSON(graph, edges[k])
    }

    graph.edges = edges

    return graph
  }

  Graph.prototype = {
    clear: function () {
      this.nodes = {}
      this.edges = {}
    },

    //serialize
    toJSON: function () {
      var nodes = [],
        edges = [],
        gNodes = this.nodes,
        gEdges = this.edges,
        k,
        from,
        to

      for (k in gNodes) {
        nodes.push(gNodes[k].toJSON())
      }

      for (from in gEdges) {
        for (to in gEdges[from]) {
          edges.push(gEdges[from][to].toJSON())
        }
      }

      return { nodes: nodes, edges: edges }
    },

    /*
     Method: getNode

     Returns a <Graph.Node> by *id*.

     Parameters:

     id - (string) A <Graph.Node> id.

     Example:

     (start code js)
       var node = graph.getNode('nodeId');
     (end code)
*/
    getNode: function (id) {
      if (this.hasNode(id)) return this.nodes[id]
      return false
    },

    /*
     Method: get

     An alias for <Graph.Util.getNode>. Returns a node by *id*.

     Parameters:

     id - (string) A <Graph.Node> id.

     Example:

     (start code js)
       var node = graph.get('nodeId');
     (end code)
*/
    get: function (id) {
      return this.getNode(id)
    },

    /*
   Method: getByName

   Returns a <Graph.Node> by *name*.

   Parameters:

   name - (string) A <Graph.Node> name.

   Example:

   (start code js)
     var node = graph.getByName('someName');
   (end code)
  */
    getByName: function (name) {
      for (var id in this.nodes) {
        var n = this.nodes[id]
        if (n.name == name) return n
      }
      return false
    },

    /*
   Method: getEdge

   Returns a <Graph.Edge> object connecting nodes with ids *id* and *id2*.

   Parameters:

   id - (string) A <Graph.Node> id.
   id2 - (string) A <Graph.Node> id.
*/
    getEdge: function (id, id2) {
      if (id in this.edges) {
        return this.edges[id][id2]
      }
      return false
    },

    /*
     Method: addNode

     Adds a node.

     Parameters:

      obj - An object with the properties described below

      id - (string) A node id
      name - (string) A node's name
      data - (object) A node's data hash

    See also:
    <Graph.Node>

  */
    addNode: function (obj) {
      if (!this.nodes[obj.id]) {
        var edges = (this.edges[obj.id] = {})
        this.nodes[obj.id] = new Graph.Node(
          merge(
            {
              id: obj.id,
              name: obj.name,
              data: merge(obj.data || {}, {}),
              adjacencies: edges,
            },
            this.opt.node
          )
        )
      }
      return this.nodes[obj.id]
    },

    /*
     Method: addEdge

     Connects nodes specified by *obj* and *obj2*. If not found, nodes are created.

     Parameters:

      obj - (object) A <Graph.Node> object.
      obj2 - (object) Another <Graph.Node> object.
      data - (object) A data object. Used to store some extra information in the <Graph.Edge> object created.

    See also:

    <Graph.Node>, <Graph.Edge>
    */
    addEdge: function (obj, obj2, data) {
      if (!this.hasNode(obj.id)) {
        this.addNode(obj)
      }
      if (!this.hasNode(obj2.id)) {
        this.addNode(obj2)
      }
      obj = this.nodes[obj.id]
      obj2 = this.nodes[obj2.id]
      if (!obj.adjacentTo(obj2)) {
        var adjsObj = (this.edges[obj.id] = this.edges[obj.id] || {})
        var adjsObj2 = (this.edges[obj2.id] = this.edges[obj2.id] || {})
        adjsObj[obj2.id] = adjsObj2[obj.id] = new Graph.Edge(obj, obj2, data, this.Edge, this.Label)
        return adjsObj[obj2.id]
      }
      return this.edges[obj.id][obj2.id]
    },

    /*
     Method: removeNode

     Removes a <Graph.Node> matching the specified *id*.

     Parameters:

     id - (string) A node's id.

    */
    removeNode: function (id) {
      if (this.hasNode(id)) {
        delete this.nodes[id]
        var adjs = this.edges[id]
        for (var to in adjs) {
          delete this.edges[to][id]
        }
        delete this.edges[id]
      }
    },

    /*
     Method: removeEdge

     Removes a <Graph.Edge> matching *id1* and *id2*.

     Parameters:

     id1 - (string) A <Graph.Node> id.
     id2 - (string) A <Graph.Node> id.
*/
    removeEdge: function (id1, id2) {
      delete this.edges[id1][id2]
      delete this.edges[id2][id1]
    },

    /*
     Method: hasNode

     Returns a boolean indicating if the node belongs to the <Graph> or not.

     Parameters:

        id - (string) Node id.
   */
    hasNode: function (id) {
      return id in this.nodes
    },

    /*
    Method: empty

    Empties the Graph

  */
    empty: function () {
      this.nodes = {}
      this.edges = {}
    },
  }

  /*
     Class: Graph.Node

     A <Graph> node.

     Implements:

     <Accessors> methods.

     The following <Graph.Util> methods are implemented by <Graph.Node>

    - <Graph.Util.eachEdge>
    - <Graph.Util.eachLevel>
    - <Graph.Util.eachSubgraph>
    - <Graph.Util.eachSubnode>
    - <Graph.Util.anySubnode>
    - <Graph.Util.getSubnodes>
    - <Graph.Util.getParents>
    - <Graph.Util.isDescendantOf>
*/
  Graph.Node = function (opt) {
    var innerOptions = {
      id: "",
      name: "",
      data: {},
      adjacencies: {},
    }
    extend(this, merge(innerOptions, opt))
  }

  Graph.Node.fromJSON = function (json) {
    return new Graph.Node(json)
  }

  Graph.Node.prototype = {
    toJSON: function () {
      return {
        id: this.id,
        name: this.name,
        data: this.serializeData(this.data),
      }
    },

    serializeData: function (data) {
      var serializedData = {},
        parents = data.parents,
        parentsCopy,
        i,
        l

      if (parents) {
        parentsCopy = Array(parents.length)
        for (i = 0, l = parents.length; i < l; ++i) {
          parentsCopy[i] = parents[i].toJSON()
        }
      }

      for (i in data) {
        serializedData[i] = data[i]
      }

      delete serializedData.parents
      delete serializedData.bundle
      serializedData = JSON.parse(JSON.stringify(serializedData))

      if (parentsCopy) {
        serializedData.parents = parentsCopy
      }

      return serializedData
    },

    /*
       Method: adjacentTo

       Indicates if the node is adjacent to the node specified by id

       Parameters:

          id - (string) A node id.

       Example:
       (start code js)
        node.adjacentTo('nodeId') == true;
       (end code)
    */
    adjacentTo: function (node) {
      return node.id in this.adjacencies
    },

    /*
       Method: getAdjacency

       Returns a <Graph.Edge> object connecting the current <Graph.Node> and the node having *id* as id.

       Parameters:

          id - (string) A node id.
    */
    getEdge: function (id) {
      return this.adjacencies[id]
    },

    /*
       Method: toString

       Returns a String with information on the Node.

    */
    toString: function () {
      return "Node(" + JSON.stringify([this.id, this.name, this.data, this.adjacencies]) + ")"
    },
  }

  /*
     Class: Graph.Edge

     A <Graph> adjacence (or edge) connecting two <Graph.Nodes>.

     Implements:

     <Accessors> methods.

     See also:

     <Graph>, <Graph.Node>

     Properties:

      nodeFrom - A <Graph.Node> connected by this edge.
      nodeTo - Another  <Graph.Node> connected by this edge.
      data - Node data property containing a hash (i.e {}) with custom options.
*/
  Graph.Edge = function (nodeFrom, nodeTo, data) {
    this.nodeFrom = nodeFrom
    this.nodeTo = nodeTo
    this.data = data || {}
  }

  Graph.Edge.fromJSON = function (graph, edgeJSON) {
    return new Graph.Edge(graph.get(edgeJSON.nodeFrom), graph.get(edgeJSON.nodeTo), edgeJSON.data)
  }

  Graph.Edge.prototype.toJSON = function () {
    return {
      nodeFrom: this.nodeFrom.id,
      nodeTo: this.nodeTo.id,
      data: this.data,
    }
  }

  /*
   Object: Graph.Util

   <Graph> traversal and processing utility object.

   Note:

   For your convenience some of these methods have also been appended to <Graph> and <Graph.Node> classes.
*/
  Graph.Util = {
    /*
       filter

       For internal use only. Provides a filtering function based on flags.
    */
    filter: function (param) {
      if (!param || !(typeof param == "string"))
        return function () {
          return true
        }
      var props = param.split(" ")
      return function (elem) {
        for (var i = 0; i < props.length; i++) {
          if (elem[props[i]]) {
            return false
          }
        }
        return true
      }
    },
    /*
       Method: getNode

       Returns a <Graph.Node> by *id*.

       Also implemented by:

       <Graph>

       Parameters:

       graph - (object) A <Graph> instance.
       id - (string) A <Graph.Node> id.

       Example:

       (start code js)
         $jit.Graph.Util.getNode(graph, 'nodeid');
         //or...
         graph.getNode('nodeid');
       (end code)
    */
    getNode: function (graph, id) {
      return graph.nodes[id]
    },

    /*
       Method: eachNode

       Iterates over <Graph> nodes performing an *action*.

       Also implemented by:

       <Graph>.

       Parameters:

       graph - (object) A <Graph> instance.
       action - (function) A callback function having a <Graph.Node> as first formal parameter.

       Example:
       (start code js)
         $jit.Graph.Util.eachNode(graph, function(node) {
          alert(node.name);
         });
         //or...
         graph.eachNode(function(node) {
           alert(node.name);
         });
       (end code)
    */
    eachNode: function (graph, action, flags) {
      var filter = this.filter(flags)
      for (var i in graph.nodes) {
        if (filter(graph.nodes[i])) action(graph.nodes[i])
      }
    },

    /*
      Method: each

      Iterates over <Graph> nodes performing an *action*. It's an alias for <Graph.Util.eachNode>.

      Also implemented by:

      <Graph>.

      Parameters:

      graph - (object) A <Graph> instance.
      action - (function) A callback function having a <Graph.Node> as first formal parameter.

      Example:
      (start code js)
        $jit.Graph.Util.each(graph, function(node) {
         alert(node.name);
        });
        //or...
        graph.each(function(node) {
          alert(node.name);
        });
      (end code)
   */
    each: function (graph, action, flags) {
      this.eachNode(graph, action, flags)
    },

    /*
       Method: eachEdge

       Iterates over <Graph.Node> adjacencies applying the *action* function.

       Also implemented by:

       <Graph.Node>.

       Parameters:

       node - (object) A <Graph.Node>.
       action - (function) A callback function having <Graph.Edge> as first formal parameter.

       Example:
       (start code js)
         $jit.Graph.Util.eachEdge(node, function(adj) {
          alert(adj.nodeTo.name);
         });
         //or...
         node.eachEdge(function(adj) {
           alert(adj.nodeTo.name);
         });
       (end code)
    */
    eachEdge: function (node, action, flags) {
      var adj = node.adjacencies,
        filter = this.filter(flags)
      for (var id in adj) {
        var a = adj[id]
        if (filter(a)) {
          if (a.nodeFrom != node) {
            var tmp = a.nodeFrom
            a.nodeFrom = a.nodeTo
            a.nodeTo = tmp
          }
          action(a, id)
        }
      }
    },

    /*
       Method: computeLevels

       Performs a BFS traversal setting the correct depth for each node.

       Also implemented by:

       <Graph>.

       Note:

       The depth of each node can then be accessed by
       >node.depth

       Parameters:

       graph - (object) A <Graph>.
       id - (string) A starting node id for the BFS traversal.
       startDepth - (optional|number) A minimum depth value. Default's 0.

    */
    computeLevels: function (graph, id, startDepth, flags) {
      startDepth = startDepth || 0
      var filter = this.filter(flags)
      this.eachNode(
        graph,
        function (elem) {
          elem._flag = false
          elem.depth = -1
        },
        flags
      )
      var root = graph.getNode(id)
      root.depth = startDepth
      var queue = [root]
      while (queue.length != 0) {
        var node = queue.pop()
        node._flag = true
        this.eachEdge(
          node,
          function (adj) {
            var n = adj.nodeTo
            if (n._flag == false && filter(n) && !adj._hiding) {
              if (n.depth < 0) n.depth = node.depth + 1 + startDepth
              queue.unshift(n)
            }
          },
          flags
        )
      }
    },

    /*
       Method: eachBFS

       Performs a BFS traversal applying *action* to each <Graph.Node>.

       Also implemented by:

       <Graph>.

       Parameters:

       graph - (object) A <Graph>.
       id - (string) A starting node id for the BFS traversal.
       action - (function) A callback function having a <Graph.Node> as first formal parameter.

       Example:
       (start code js)
         $jit.Graph.Util.eachBFS(graph, 'mynodeid', function(node) {
          alert(node.name);
         });
         //or...
         graph.eachBFS('mynodeid', function(node) {
           alert(node.name);
         });
       (end code)
    */
    eachBFS: function (graph, id, action, flags) {
      var filter = this.filter(flags)
      this.clean(graph)
      var queue = [graph.getNode(id)]
      while (queue.length != 0) {
        var node = queue.pop()
        if (!node) return
        node._flag = true
        action(node, node.depth)
        this.eachEdge(
          node,
          function (adj) {
            var n = adj.nodeTo
            if (n._flag == false && filter(n) && !adj._hiding) {
              n._flag = true
              queue.unshift(n)
            }
          },
          flags
        )
      }
    },

    /*
       Method: eachLevel

       Iterates over a node's subgraph applying *action* to the nodes of relative depth between *levelBegin* and *levelEnd*.
       In case you need to break the iteration, *action* should return false.

       Also implemented by:

       <Graph.Node>.

       Parameters:

       node - (object) A <Graph.Node>.
       levelBegin - (number) A relative level value.
       levelEnd - (number) A relative level value.
       action - (function) A callback function having a <Graph.Node> as first formal parameter.

    */
    eachLevel: function (node, levelBegin, levelEnd, action, flags) {
      var d = node.depth,
        filter = this.filter(flags),
        that = this,
        shouldContinue = true
      levelEnd = levelEnd === false ? Number.MAX_VALUE - d : levelEnd
      ;(function loopLevel(node, levelBegin, levelEnd) {
        if (!shouldContinue) return
        var d = node.depth,
          ret
        if (d >= levelBegin && d <= levelEnd && filter(node)) ret = action(node, d)
        if (typeof ret !== "undefined") shouldContinue = ret
        if (shouldContinue && d < levelEnd) {
          that.eachEdge(node, function (adj) {
            var n = adj.nodeTo
            if (n.depth > d) loopLevel(n, levelBegin, levelEnd)
          })
        }
      })(node, levelBegin + d, levelEnd + d)
    },

    /*
       Method: eachSubgraph

       Iterates over a node's children recursively.

       Also implemented by:

       <Graph.Node>.

       Parameters:
       node - (object) A <Graph.Node>.
       action - (function) A callback function having a <Graph.Node> as first formal parameter.

       Example:
       (start code js)
         $jit.Graph.Util.eachSubgraph(node, function(node) {
           alert(node.name);
         });
         //or...
         node.eachSubgraph(function(node) {
           alert(node.name);
         });
       (end code)
    */
    eachSubgraph: function (node, action, flags) {
      this.eachLevel(node, 0, false, action, flags)
    },

    /*
       Method: eachSubnode

       Iterates over a node's children (without deeper recursion).

       Also implemented by:

       <Graph.Node>.

       Parameters:
       node - (object) A <Graph.Node>.
       action - (function) A callback function having a <Graph.Node> as first formal parameter.

       Example:
       (start code js)
         $jit.Graph.Util.eachSubnode(node, function(node) {
          alert(node.name);
         });
         //or...
         node.eachSubnode(function(node) {
           alert(node.name);
         });
       (end code)
    */
    eachSubnode: function (node, action, flags) {
      this.eachLevel(node, 1, 1, action, flags)
    },

    /*
       Method: anySubnode

       Returns *true* if any subnode matches the given condition.

       Also implemented by:

       <Graph.Node>.

       Parameters:
       node - (object) A <Graph.Node>.
       cond - (function) A callback function returning a Boolean instance. This function has as first formal parameter a <Graph.Node>.

       Example:
       (start code js)
         $jit.Graph.Util.anySubnode(node, function(node) { return node.name == "mynodename"; });
         //or...
         node.anySubnode(function(node) { return node.name == 'mynodename'; });
       (end code)
    */
    anySubnode: function (node, cond, flags) {
      var flag = false
      cond =
        cond ||
        function () {
          return true
        }
      var c =
        typeof cond == "string"
          ? function (n) {
              return n[cond]
            }
          : cond
      this.eachSubnode(
        node,
        function (elem) {
          if (c(elem)) flag = true
        },
        flags
      )
      return flag
    },

    /*
       Method: getSubnodes

       Collects all subnodes for a specified node.
       The *level* parameter filters nodes having relative depth of *level* from the root node.

       Also implemented by:

       <Graph.Node>.

       Parameters:
       node - (object) A <Graph.Node>.
       level - (optional|number) Default's *0*. A starting relative depth for collecting nodes.

       Returns:
       An array of nodes.

    */
    getSubnodes: function (node, level, flags) {
      var ans = [],
        that = this
      level = level || 0
      var levelStart, levelEnd
      if (Array.isArray(level) == "array") {
        levelStart = level[0]
        levelEnd = level[1]
      } else {
        levelStart = level
        levelEnd = Number.MAX_VALUE - node.depth
      }
      this.eachLevel(
        node,
        levelStart,
        levelEnd,
        function (n) {
          ans.push(n)
        },
        flags
      )
      return ans
    },

    /*
       Method: getParents

       Returns an Array of <Graph.Nodes> which are parents of the given node.

       Also implemented by:

       <Graph.Node>.

       Parameters:
       node - (object) A <Graph.Node>.

       Returns:
       An Array of <Graph.Nodes>.

       Example:
       (start code js)
         var pars = $jit.Graph.Util.getParents(node);
         //or...
         var pars = node.getParents();

         if(pars.length > 0) {
           //do stuff with parents
         }
       (end code)
    */
    getParents: function (node) {
      var ans = []
      this.eachEdge(node, function (adj) {
        var n = adj.nodeTo
        if (n.depth < node.depth) ans.push(n)
      })
      return ans
    },

    /*
    Method: isDescendantOf

    Returns a boolean indicating if some node is descendant of the node with the given id.

    Also implemented by:

    <Graph.Node>.


    Parameters:
    node - (object) A <Graph.Node>.
    id - (string) A <Graph.Node> id.

    Example:
    (start code js)
      $jit.Graph.Util.isDescendantOf(node, "nodeid"); //true|false
      //or...
      node.isDescendantOf('nodeid');//true|false
    (end code)
 */
    isDescendantOf: function (node, id) {
      if (node.id == id) return true
      var pars = this.getParents(node),
        ans = false
      for (var i = 0; !ans && i < pars.length; i++) {
        ans = ans || this.isDescendantOf(pars[i], id)
      }
      return ans
    },

    /*
     Method: clean

     Cleans flags from nodes.

     Also implemented by:

     <Graph>.

     Parameters:
     graph - A <Graph> instance.
  */
    clean: function (graph) {
      this.eachNode(graph, function (elem) {
        elem._flag = false
      })
    },
  }

  //Append graph methods to <Graph>
  ;["get", "getNode", "each", "eachNode", "computeLevels", "eachBFS", "clean"].forEach(function (
    m
  ) {
    Graph.prototype[m] = function () {
      return Graph.Util[m].apply(Graph.Util, [this].concat(Array.prototype.slice.call(arguments)))
    }
  })

  //Append node methods to <Graph.Node>
  ;[
    "eachEdge",
    "eachLevel",
    "eachSubgraph",
    "eachSubnode",
    "anySubnode",
    "getSubnodes",
    "getParents",
    "isDescendantOf",
  ].forEach(function (m) {
    Graph.Node.prototype[m] = function () {
      return Graph.Util[m].apply(Graph.Util, [this].concat(Array.prototype.slice.call(arguments)))
    }
  })

  window.Graph = Graph
})()
